#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int maxSubArray(vector<int>& nums) {
    const int INF = 0x3f3f3f3f;
    int n = nums.size();
    vector<int> f(n + 1, -INF);
    int res = -INF;
    for (int i = 1; i <= n; i++)
    {
        f[i] = max(f[i - 1], 0) + nums[i - 1];
        res = max(res, f[i]);
    }
    return res;
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

void flatten(TreeNode* root) {
    if (!root)   return;
    auto dfs = [&](auto&& dfs, TreeNode* root)->TreeNode*
    {
        auto left = root->left, right = root->right;
        TreeNode* last = root;
        root->left = nullptr;
        if (left)
        {
            root->right = left;
            last = dfs(dfs, left);
        }
        if (right)
        {
            last->right = right;
            last = dfs(dfs, right);
        }
        return last;
    };
    dfs(dfs, root);
}